We investigate the computational complexity of the problem of counting themaximal satisfying assignments of a Constraint Satisfaction Problem (CSP) overthe Boolean domain {0,1}. A satisfying assignment is maximal if any newassignment which is obtained from it by changing a 0 to a 1 is unsatisfying.For each constraint language Gamma, #MaximalCSP(Gamma) denotes the problem ofcounting the maximal satisfying assignments, given an input CSP withconstraints in Gamma. We give a complexity dichotomy for the problem of exactlycounting the maximal satisfying assignments and a complexity trichotomy for theproblem of approximately counting them. Relative to the problem #CSP(Gamma),which is the problem of counting all satisfying assignments, the maximalversion can sometimes be easier but never harder. This finding contrasts withthe recent discovery that approximately counting maximal independent sets in abipartite graph is harder (under the usual complexity-theoretic assumptions)than counting all independent sets.
展开▼
